Most computer based data transmission systems and data storage systems provide at least the ability to detect transmission and storage errors to prevent corrupted data from being accepted. Such error detection systems use "error detection" encoding techniques. The most commonly used error detection encoding technique makes use of error detection data called cyclic redundancy codes (CRCs), which are widely used due to their ease of computation and reliable error detection.
Erasure resilient codes, which enable lossless data recovery despite loss of information in transmission or storage, are also well known, although somewhat less widely used than error detection codes. For instance, Hamming codes and Reed-Solomon codes are two well known examples of erasure resilient codes. The corresponding data encoding techniques add redundant information to stored or transmitted data. Reed-Solomon codes are used in many magnetic disk storage systems.
In general, the amount of redundant data added to transmitted or stored data by such redundancy encoding techniques varies from system to system. Adding more redundant data allows lossless recovery of data with higher error or data loss rates than adding less redundant data, but reduces the transmission or storage efficiency of the associated system.
In real time data transmission systems, it is common to find that some parts of transmitted data are more important than other parts of the transmitted data. We will call a part consisting of equally important transmitted data a "unit". It is also common that units of different importance that are naturally related to each other are grouped together to constitute what we herein call a "message" or "logical message". Furthermore, it is quite common that the information in the less important units of a message are of no practical use without the information in the more important units, i.e., the less important units are critically dependent on the more important units.
In some previous systems known to the inventors of the present invention that use loss recovery encoding techniques, a single level of redundancy encoding is used for all data of each message transmitted or stored in each such system. For instance, known disk drive storage systems each use a single version of the Reed-Solomon encoding technique with a single level of data redundancy. Such systems are inefficient in terms of the total bandwidth required due to using the same level of importance for all units independent of their importance. Such systems tend to either (A) add less than the ideal amounts of redundancy to critical data due to the cost of adding such redundancy to the entire message, or (B) waste resources by adding redundancy to the entire message based on the level of redundancy needed for the most critical data.
All other prior systems known to the inventors have partitioned the data stream into units, and redundantly encoded each unit using a single level of redundancy according to its importance. Under some data loss conditions, such systems may suffer from the loss of the more important units within a message even when the less important dependent units get through.
It is an object of the present invention to allow the flexibility of using multilevel redundancy encoding over the entire message so as to guarantee acquisition of the units within the message in order of importance under any data loss conditions.
It is a primary object of the present invention to provide systems that efficiently add redundancy data to messages. It is a related object of the present invention to provide systems that encode different portions of a data stream with two or more different non-zero levels of redundant data such that portions of the data stream denoted as having higher priority are encoded with a higher level of redundant data than portions of the data stream denoted as having lower priority.
Another object of the present invention is to provide a system that accepts priority data regarding specified portions of a specified data stream and automatically scales the level of redundancy with which the various data stream portions are encoded in accordance with the priority data.
Another object of the present invention is to provide systems that automatically decode and recover received data encoded with multiple levels of redundant data.
Still another object of the present invention is to provide a hierarchical or priority level based data filtering subsystem for use in a data distribution system having one or more data distribution subsystems with insufficient available data bandwidth to transmit data streams that other portions of the data distribution system can handle. More specifically,, it is an objective of the present invention to provide a data filtering subsystem that automatically transmits only the highest priority portions of such data streams into low bandwidth portions of the data distribution system.
Another object of the present invention is to simplify network communication protocols by making application programs responsible for redundant data encoding and decoding, while the network level software handles only data transmission on corrupted data detection through the use of standard CRC codes or the like.